package com.gxc.array;

import java.util.*;

/**
 * 47. 全排列 II
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 */
public class PermuteUnique {

    public static void main(String[] args) {
/*        List<List<Integer>> permute = handle(new int[]{1, 2, 3});
        print(permute);*/
        int[] nums = new int[]{1, 1, 2};
        List<List<Integer>> permute = handle(nums);
        List<List<Integer>> list = process(permute, nums);
        print(list);
    }

    public static List<List<Integer>> handle(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        recursion(0 , nums, list, res);
        return res;
    }

    public static void recursion(int i, int[] num, List<Integer> list, List<List<Integer>> res) {
        if (i == num.length) {
            res.add(new ArrayList<>(list));
            return;
        }

        Set<Integer> set = new HashSet<>();
        for (int j = 0; j < num.length; j++) {
            if (list.contains(j) || set.contains(num[j])) continue;
            list.add(j);
            set.add(num[j]);
            recursion(i+1, num, list, res);
            list.remove((Object)j);
        }
    }

    private static List<List<Integer>> process(List<List<Integer>> permute, int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < permute.size(); i++) {
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j < permute.get(i).size(); j++) {
                list.add(nums[permute.get(i).get(j)]);
            }
            res.add(list);
        }
        return res;
    }

    private static void print(List<List<Integer>> list) {
        for (int i = 0; i < list.size(); i++) {
            List<Integer> list1 = list.get(i);
            for (int j = 0; j < list1.size(); j++) {
                System.out.print(list1.get(j) + " ");
            }
            System.out.println("");
        }
    }

    class Solution {
        boolean[] vis;

        public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> ans = new ArrayList<List<Integer>>();
            List<Integer> perm = new ArrayList<Integer>();
            vis = new boolean[nums.length];
            Arrays.sort(nums);
            backtrack(nums, ans, 0, perm);
            return ans;
        }

        public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {
            if (idx == nums.length) {
                ans.add(new ArrayList<Integer>(perm));
                return;
            }
            for (int i = 0; i < nums.length; ++i) {
                /**
                 * 【同层剪枝】
                 * 当选取到nums[i]，并满足 i > 0 && nums[i - 1] == nums[i] 时，
                 * 若 !visited[i - 1] = true，说明以nums[i - 1]为某一层元素的选择已穷尽，
                 * 以至于在回溯的时候置 visited[i - 1] = false）。于是后续会根据这个条件跳过同层相等元素。
                 *
                 * 【非同层剪枝】
                 * 最后一个子条件若采用 visited[i - 1]，
                 * 当选取到nums[i]，并满足 i > 0 && nums[i - 1] == nums[i] 时，
                 * 若 visited[i - 1] = true，表明当前是在nums[i - 1]的子树中选择nums[i]，
                 * 根据这个条件，在子树中遇到nums[i]，总是不选取（continue），
                 * 那么该子树总是无法提供有效排列（因为缺少nums[i]），
                 * 于是对该子树的搜索都是无效的。
                 * 之后回溯到nums[i - 1]所在层后，
                 * 由于撤销为 visited[i - 1] = false，不再满足visited[i - 1] = true，
                 * 于是不会跳过，可以正常选取到包含nums[i - 1]和nums[i]的排列。
                 *
                 * 通过上述说明，采用!visited[i - 1]的「同层剪枝」效率更高，
                 * 因为「非同层剪枝」对nums[i - 1]的子树（存在nums[i] == nums[i - 1]）的搜索是无效的。
                 * 另外我们也可以看到，无论哪一种，输出有效排列的顺序是一致的。二者的差别可理解为，
                 * 非同层剪枝比同层剪枝多做了无效子树搜索动作。
                 */
                if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                    continue;
                }
                perm.add(nums[i]);
                vis[i] = true;
                backtrack(nums, ans, idx + 1, perm);
                vis[i] = false;
                perm.remove(idx);
            }
        }
    }


}
